# BFS
# class Solution(object):
#     def kSimilarity(self, s1, s2):
#         k = 0
#         if s1 == s2:
#             return 0
#         now_st = {s1}
#         n = len(s1)
#         while True:
#             k += 1
#             next_st = set()
#             for s in now_st:
#                 for i in range(n):
#                     if s[i] == s2[i]:
#                         continue
#                     else:
#                         for j in range(i + 1, n):
#                             if s[j] == s2[i] and s[j] != s2[j]:
#                                 new_s = s[: i] + s[j] + s[i + 1: j] + s[i] + s[j + 1:]
#                                 if new_s == s2:
#                                     return k
#                                 else:
#                                     next_st.add(new_s)
#                         break
#             now_st = next_st


# DFS
import functools
class Solution(object):
    def kSimilarity(self, s1, s2):
        @functools.cache
        def dfs(t1, t2):
            if t1 == t2:
                return 0
            else:
                m = len(t1)
                if t1[0] == t2[0]:
                    return dfs(t1[1:], t2[1:])
                else:
                    min_val = float('inf')
                    for i in range(1, m):
                        if t1[i] == t2[0] and t1[i] != t2[i]:
                            new_t1 = t1[1: i] + t1[0] + t1[i + 1:]
                            min_val = min(min_val, dfs(new_t1, t2[1:]) + 1)
                    return min_val

        return dfs(s1, s2)


data = Solution()
s1 = "abab"
s2 = "baba"
print(data.kSimilarity(s1, s2))
s1 = "aabbccddee"
s2 = "cdacbeebad"
print(data.kSimilarity(s1, s2))
